//#include <iostream>
//using namespace std;
//
//const int N = 110;
//
//int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
//int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
//
//int n, m;
//char a[N][N];
//bool st[N][N] = { 0 };
//
//void dfs(int i, int j)
//{
//	st[i][j] = 1;
//
//	for (int k = 0; k < 8; k++)
//	{
//		int x = i + dx[k];
//		int y = j + dy[k];
//
//		if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == 'W' && st[x][y] == 0)
//		{
//			dfs(x, y);
//		}
//	}
//}
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//
//	int ret = 0;
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (a[i][j] == 'W' && st[i][j] == 0)
//			{
//				ret++;
//				dfs(i, j);
//			}
//		}
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}



//#include <iostream>
//using namespace std;
//
//const int N = 35;
//
//int dx[] = { 0, 0, 1, -1 };
//int dy[] = { 1, -1, 0, 0 };
//int n = 0;
//int a[N][N];
//bool st[N][N];
//
//void dfs(int i, int j)
//{
//	st[i][j] = 1;
//	
//	for (int k = 0; k < 4; k++)
//	{
//		int x = i + dx[k];
//		int y = j + dy[k];
//
//		if (x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1 && a[x][y] == 0 && st[x][y] == 0)
//		{
//			dfs(x, y);
//		}
//	}
//}
//
//int main()
//{
//	
//	while (cin >> n)
//	{
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= n; j++)
//			{
//				cin >> a[i][j];
//			}
//		}
//
//		dfs(0, 0);
//
//		for (int i = 1; i <= n; i++)
//		{
//			for (int j = 1; j <= n; j++)
//			{
//				if (st[i][j] == 1)
//					cout << 0 << " ";
//				else if (a[i][j] == 1)
//					cout << 1 << " ";
//				else
//					cout << 2 << " ";
//			}
//			cout << endl;
//		}
//	}
//
//
//
//	return 0;
//}

//
//#include <iostream>
//#include <string>
//using namespace std;
//
//string path;
//int n;
//
//void dfs(int pos)
//{
//	if (pos > n)
//	{
//		cout << path << endl;
//		return;
//	}
//
//	path += 'N';
//	dfs(pos + 1);
//	path.pop_back();
//
//	path += 'Y';
//	dfs(pos + 1);
//	path.pop_back();
//
//}
//
//int main()
//{
//	cin >> n;
//
//	dfs(1);
//
//	return 0;
//}

//
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int n, m;
//
//vector<int> path;
//
//void dfs(int begin)
//{
//	int pos = path.size();
//	if (pos == m)
//	{
//		for (const auto& ch : path)
//		{
//			cout << ch << " ";
//		}
//		cout << endl;
//		return;
//	}
//
//	for (int i = begin; i <= n; i++)
//	{
//		path.push_back(i);
//		dfs(i + 1);
//		path.pop_back();
//	}
//}
//
//int main()
//{
//	cin >> n >> m;
//	
//	dfs(1);
//
//	return 0;
//}


//#include <iostream>
//#include <vector>
//using namespace std;
//
//vector<int> path;
//bool st[15] = { 0 };
//
//int n, m;
//
//void dfs()
//{
//	if (path.size() == m)
//	{
//		for (const auto& ch : path)
//		{
//			cout << ch << " ";
//		}
//		cout << endl;
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (st[i] == 1)
//			continue;
//
//		path.push_back(i);
//		st[i] = 1;
//		dfs();
//		st[i] = 0;
//		path.pop_back();
//	}
//}
//
//int main()
//{
//	cin >> n >> m;
//
//	dfs();
//
//	return 0;
//}

//
//#include <iostream>
//#include <vector>
//using namespace std;
//
//vector<int> path;
//bool st[12] = { 0 };
//
//int n;
//
//void dfs()
//{
//	if (path.size() == n)
//	{
//		for (const auto& ch : path)
//		{
//			printf("%5d", ch);
//		}
//		cout << endl;
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (st[i] == 0)
//		{
//			st[i] = 1;
//			path.push_back(i);
//			dfs();
//			path.pop_back();
//			st[i] = 0;
//		}
//		
//	}
//
//}
//
//int main()
//{
//	cin >> n;
//	dfs();
//
//	return 0;
//}